package com.github.yangyishe;

/**
 * 707. 设计链表
 * https://leetcode.cn/problems/design-linked-list/
 * 做出来即可, 设计问题就不讲效率了. 为了效率会导致代码看的不清晰
 *
 *
 * 你可以选择使用单链表或者双链表，设计并实现自己的链表。
 *
 * 单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
 *
 * 如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
 *
 * 实现 MyLinkedList 类：
 *
 * MyLinkedList() 初始化 MyLinkedList 对象。
 * int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
 * void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
 * void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
 * void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
 * void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。
 *
 *
 * 示例：
 *
 * 输入
 * ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
 * [[], [1], [3], [1, 2], [1], [1], [1]]
 * 输出
 * [null, null, null, null, 2, null, 3]
 *
 * 解释
 * MyLinkedList myLinkedList = new MyLinkedList();
 * myLinkedList.addAtHead(1);
 * myLinkedList.addAtTail(3);
 * myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
 * myLinkedList.get(1);              // 返回 2
 * myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
 * myLinkedList.get(1);              // 返回 3
 *
 *
 * 提示：
 *
 * 0 <= index, val <= 1000
 * 请不要使用内置的 LinkedList 库。
 * 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。
 */
public class Problem707 {
    public static void main(String[] args) {
//        MyLinkedList myLinkedList = new MyLinkedList();
//        myLinkedList.addAtHead(1);
//        myLinkedList.addAtTail(3);
//        myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
//        System.out.println(myLinkedList.get(1));              // 返回 2
//        myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
//        System.out.println(myLinkedList.get(1));              // 返回 3

        //["MyLinkedList",
        MyLinkedList myLinkedList = new MyLinkedList();
        // "addAtHead",
        myLinkedList.addAtHead(1);
        // "addAtTail",
        myLinkedList.addAtTail(3);
        // "addAtIndex",
        myLinkedList.addAtIndex(1,2);
        // "get",
        System.out.println(myLinkedList.get(1));
        // "deleteAtIndex",
        myLinkedList.deleteAtIndex(1);
        // "get",
        System.out.println(myLinkedList.get(1));
        // "get",
        System.out.println(myLinkedList.get(3));
        // "deleteAtIndex",
        myLinkedList.deleteAtIndex(3);
        // "deleteAtIndex",
        myLinkedList.deleteAtIndex(0);
        // "get",
        System.out.println(myLinkedList.get(0));
        // "deleteAtIndex",
        myLinkedList.deleteAtIndex(0);
        // "get"]
        System.out.println(myLinkedList.get(0));
        //[[],[1],[3],[1,2],[1],[1],[1],[3],[3],[0],[0],[0],[0]]

    }
}

class MyLinkedList {

    private MyLinkedListNode root;

    public MyLinkedList() {

    }

    /**
     * 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
     * @param index
     * @return
     */
    public int get(int index) {
        if (root==null) {
            return -1;
        }
        MyLinkedListNode descendent = root.findDescendent(index);
        if (descendent!=null) {
            return descendent.getVal();
        }else{
            return -1;
        }

    }

    /**
     * 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
     * @param val
     */
    public void addAtHead(int val) {
        MyLinkedListNode myLinkedListNode = new MyLinkedListNode(val);
        if (root==null) {
            root=myLinkedListNode;
        }else{
            myLinkedListNode.setNext(root);
            root.setPrev(myLinkedListNode);
            root=myLinkedListNode;
        }
    }

    /**
     * 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
     * @param val
     */
    public void addAtTail(int val) {
        MyLinkedListNode myLinkedListNode = new MyLinkedListNode(val);
        if(root==null){
            root=myLinkedListNode;
        }else{
            MyLinkedListNode leaf = root.findLeaf();
            leaf.setNext(myLinkedListNode);
            myLinkedListNode.setPrev(leaf);
        }
    }

    /**
     * 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
     * @param index
     * @param val
     */
    public void addAtIndex(int index, int val) {
        MyLinkedListNode myLinkedListNode = new MyLinkedListNode(val);
        if (root==null) {
            if(index==0){
                root=myLinkedListNode;
            }else{
                return;
            }
        }else{
            int size = root.afterSize() + 1;
            if(size==index){
                MyLinkedListNode leaf = root.findLeaf();
                leaf.setNext(myLinkedListNode);
                myLinkedListNode.setPrev(leaf);
            }else if(size>index){
                MyLinkedListNode descendent = root.findDescendent(index);
                MyLinkedListNode prev = descendent.getPrev();

                if(prev==null){
                    addAtHead(val);
                }else{
                    prev.setNext(myLinkedListNode);
                    myLinkedListNode.setNext(descendent);

                    myLinkedListNode.setPrev(prev);
                    descendent.setPrev(myLinkedListNode);
                }

            }else{
                return;
            }

        }
    }

    /**
     * 如果下标有效，则删除链表中下标为 index 的节点。
     * @param index
     */
    public void deleteAtIndex(int index) {
        if (root==null) {
            return;
        }else{
            MyLinkedListNode descendent = root.findDescendent(index);
            if(descendent==null){
                return;
            }
            MyLinkedListNode prev = descendent.getPrev();
            // 处理getNext或getPrev的后续方法时, 尤其要注意是否为null的问题
            if (prev==null) {
                root=descendent.getNext();
                if (descendent.getNext()!=null) {
                    descendent.getNext().setPrev(null);
                }
            }else{
                prev.setNext(descendent.getNext());
                if(descendent.getNext()!=null){
                    descendent.getNext().setPrev(prev);
                }
            }
        }
    }
}

class MyLinkedListNode{
    private final int val;
    private MyLinkedListNode next;
    private MyLinkedListNode prev;

    public MyLinkedListNode getNext() {
        return next;
    }

    public void setNext(MyLinkedListNode next) {
        this.next = next;
    }

    public MyLinkedListNode getPrev() {
        return prev;
    }

    public void setPrev(MyLinkedListNode prev) {
        this.prev = prev;
    }

    public int getVal() {
        return val;
    }

    public MyLinkedListNode(int val) {
        this.val = val;
    }

    /**
     * 查找后代
     * 在对象的递归方法内, 尤其要注意引用递归方法的对象所指. 以防万一, 即使是当前方法, 也应当指明自身this.
     * @param offset
     * @return
     */
    public MyLinkedListNode findDescendent(int offset){
        if(offset==0){
            return this;
        }
        if(next==null){
            return null;
        }
        return next.findDescendent(offset-1);
    }

    /**
     * 找到叶子节点
     * @return
     */
    public MyLinkedListNode findLeaf(){
        if (next==null) {
            return this;
        }else{
            return next.findLeaf();
        }
    }

    /**
     * 之后的数量. 不包含当前数量
     * @return
     */
    public int afterSize(){
        if(next==null){
            return 0;
        }else{
            return next.afterSize()+1;
        }
    }

}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
